package primary.primary0;

public class S0025K个一组翻转链表 {


    /**
     * 自己看了一下，这个翻转，可以不通过两两交换来做，而是逐个把当前值往前扔
     * 比如k = 3,
     * 反转 1 2 3
     * 先吧2往前扔 变成 2 1 3，然后指针移到3，把3往前扔 变成 3 2 1，这样就实现翻转了
     */


    /**
     * 答案，没有开辟新的存储空间(实际上listNode[]也不算新的存储空间)
     * 看的稀里糊涂
     */
    class Solution2 {
        public ListNode reverseKGroup(ListNode head, int k) {
            ListNode hair = new ListNode(0);
            hair.next = head;
            ListNode pre = hair;

            while (head != null) {
                ListNode tail = pre;
                // 查看剩余部分长度是否大于等于 k
                for (int i = 0; i < k; ++i) {
                    tail = tail.next;
                    if (tail == null) {
                        return hair.next;
                    }
                }
                ListNode nex = tail.next;
                ListNode[] reverse = myReverse(head, tail);
                head = reverse[0];
                tail = reverse[1];
                // 把子链表重新接回原链表
                pre.next = head;
                tail.next = nex;
                pre = tail;
                head = tail.next;
            }

            return hair.next;
        }

        public ListNode[] myReverse(ListNode head, ListNode tail) {
            ListNode prev = tail.next;
            ListNode p = head;
            while (prev != tail) {
                ListNode nex = p.next;
                p.next = prev;
                prev = p;
                p = nex;
            }
            return new ListNode[]{tail, head};
        }
    }



    /**
     * 100
     * 我的做法和0024 两两交换几乎一样
     */
    class Solution {
        public ListNode reverseKGroup(ListNode head, int k) {
            ListNode fakeHead = new ListNode();
            fakeHead.next = head;
            reverseHelp(fakeHead, k);
            return fakeHead.next;
        }

        public void reverseHelp(ListNode node, int k){
            if(node == null || k <= 1){
                return;
            }
            int avaialCount = k;
            boolean canReverse = true;
            ListNode temp = node;
            while(--avaialCount >= 0){
                temp = temp.next;
                if(temp == null){
                    canReverse = false;
                    break;
                }
            }
            if(!canReverse){
                return;
            }
            // 反转过来可以用递归去做，避免额外的存储空间(其实也没有，就是要创建个ListNode[]，空间还是本来的)
            // 不过递归的话也不能处理任意长度的，毕竟java栈也是有深度限制的
            ListNode[] toReverse = new ListNode[k];
            temp = node;
            for(int i = 0; i <k; i++){
                toReverse[i] = temp.next;
                temp = temp.next;
            }
            ListNode tail = temp.next;
            temp = node;
            for(int i = 0; i < k; i++){
                temp.next = toReverse[k - i - 1];
                temp = temp.next;
            }
            temp.next = tail;
            reverseHelp(temp, k);
        }

    }
}
